{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Longest Subsequence Repeated k Times"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #string #backtracking #counting #enumeration"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #字符串 #回溯 #计数 #枚举"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: longestSubsequenceRepeatedK"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #重复 K 次的最长子序列"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个长度为 <code>n</code> 的字符串 <code>s</code> ，和一个整数 <code>k</code> 。请你找出字符串 <code>s</code> 中 <strong>重复</strong> <code>k</code> 次的 <strong>最长子序列</strong> 。</p>\n",
    "\n",
    "<p><strong>子序列</strong> 是由其他字符串删除某些（或不删除）字符派生而来的一个字符串。</p>\n",
    "\n",
    "<p>如果&nbsp;<code>seq * k</code> 是 <code>s</code> 的一个子序列，其中 <code>seq * k</code> 表示一个由 <code>seq</code> 串联 <code>k</code>&nbsp;次构造的字符串，那么就称 <code>seq</code><strong> </strong>是字符串 <code>s</code> 中一个 <strong>重复 <code>k</code> 次</strong> 的子序列。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>举个例子，<code>\"bba\"</code> 是字符串 <code>\"bababcba\"</code> 中的一个重复 <code>2</code> 次的子序列，因为字符串 <code>\"bbabba\"</code> 是由 <code>\"bba\"</code> 串联 <code>2</code> 次构造的，而&nbsp;<code>\"bbabba\"</code> 是字符串 <code>\"<em><strong>b</strong></em>a<em><strong>bab</strong></em>c<em><strong>ba</strong></em>\"</code> 的一个子序列。</li>\n",
    "</ul>\n",
    "\n",
    "<p>返回字符串 <code>s</code> 中 <strong>重复 k 次的最长子序列</strong>&nbsp; 。如果存在多个满足的子序列，则返回 <strong>字典序最大</strong> 的那个。如果不存在这样的子序列，返回一个 <strong>空</strong> 字符串。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"example 1\" src=\"https://assets.leetcode.com/uploads/2021/08/30/longest-subsequence-repeat-k-times.png\" style=\"width: 457px; height: 99px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"letsleetcode\", k = 2\n",
    "<strong>输出：</strong>\"let\"\n",
    "<strong>解释：</strong>存在两个最长子序列重复 2 次：let\" 和 \"ete\" 。\n",
    "\"let\" 是其中字典序最大的一个。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"bb\", k = 2\n",
    "<strong>输出：</strong>\"b\"\n",
    "<strong>解释：</strong>重复 2 次的最长子序列是 \"b\" 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"ab\", k = 2\n",
    "<strong>输出：</strong>\"\"\n",
    "<strong>解释：</strong>不存在重复 2 次的最长子序列。返回空字符串。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == s.length</code></li>\n",
    "\t<li><code>2 &lt;= k &lt;= 2000</code></li>\n",
    "\t<li><code>2 &lt;= n &lt; k * 8</code></li>\n",
    "\t<li><code>s</code> 由小写英文字母组成</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [longest-subsequence-repeated-k-times](https://leetcode.cn/problems/longest-subsequence-repeated-k-times/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [longest-subsequence-repeated-k-times](https://leetcode.cn/problems/longest-subsequence-repeated-k-times/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"letsleetcode\"\\n2', '\"bb\"\\n2', '\"ab\"\\n2']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubsequenceRepeatedK(self, s: str, k: int) -> str:\n",
    "        cnt = collections.Counter(s)\n",
    "        s1 = \"\".join([x*(cnt[x]//k) for x in sorted(cnt,reverse=True)])\n",
    "        length = len(s) if len(s)<=7 else 7\n",
    "        for i in range(length,0,-1):\n",
    "            for s2 in permutations(s1,i):\n",
    "                res = \"\".join(s2)\n",
    "                s3 = iter(s)\n",
    "                if all(i in s3 for i in s2*k):\n",
    "                    return res\n",
    "        return \"\"\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubsequenceRepeatedK(self, s: str, k: int) -> str:\n",
    "        num = Counter(s)\n",
    "        hot = ''.join(ele * (num[ele] // k) for ele in sorted(num, reverse=True))\n",
    "        for i in range(len(hot), 0, -1):\n",
    "            for item in permutations(hot, i):\n",
    "                word = ''.join(item)\n",
    "                ss = iter(s)\n",
    "                if all(c in ss for c in word * k):\n",
    "                    return word\n",
    "        return ''\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubsequenceRepeatedK(self, s: str, k: int) -> str:\n",
    "        num = Counter(s)\n",
    "        hot = ''.join(ele * (num[ele] // k) for ele in sorted(num, reverse=True))\n",
    "        for i in range(len(hot), 0, -1):\n",
    "            for item in permutations(hot, i):\n",
    "                word = ''.join(item)\n",
    "                ss = iter(s)\n",
    "                if all(c in ss for c in word * k):\n",
    "                    return word\n",
    "        return ''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "import itertools\n",
    "\n",
    "class Solution:\n",
    "    def longestSubsequenceRepeatedK(self, s: str, k: int) -> str:\n",
    "        # 计算每个字符的频率\n",
    "        num_freq = collections.Counter(s)\n",
    "        \n",
    "        # 创建一个字符串，其中包含那些出现次数至少为k的字符\n",
    "        avai_chrs = ''.join(x * (num_freq[x] // k) for x in sorted(num_freq, reverse=True))\n",
    "        \n",
    "        # 从最长的子序列开始，尝试所有可能的排列\n",
    "        for i in range(len(avai_chrs), 0, -1):\n",
    "            for word in map(''.join, itertools.permutations(avai_chrs, i)):\n",
    "                ss = iter(s)\n",
    "                # 检查子序列是否在s中重复k次\n",
    "                if all(c in ss for c in word * k):\n",
    "                    return word\n",
    "        return ''\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "from itertools import permutations\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def longestSubsequenceRepeatedK(self, s: str, k: int) -> str:\n",
    "        cnt = Counter(s)\n",
    "        hot = ''.join([w * (cnt[w] // k) for w in sorted(cnt, reverse=True)])\n",
    "        m = len(hot)\n",
    "        for i in range(m, 0, -1):\n",
    "            for item in permutations(hot, i):\n",
    "                word = \"\".join(item)\n",
    "                ss = iter(s)\n",
    "                if all(w in ss for w in word*k):\n",
    "                    return word\n",
    "        return ''\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def longestSubsequenceRepeatedK(self, s: str, k: int) -> str:\r\n",
    "        num = Counter(s)\r\n",
    "        hot = ''.join(ele * (num[ele] // k) for ele in sorted(num, reverse=True))\r\n",
    "        for i in range(len(hot), 0, -1):\r\n",
    "            for item in permutations(hot, i):\r\n",
    "                word = ''.join(item)\r\n",
    "                ss = iter(s)\r\n",
    "                if all(c in ss for c in word * k):\r\n",
    "                    return word\r\n",
    "        return ''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubsequenceRepeatedK(self, s: str, k: int) -> str:\n",
    "        cnt = Counter(s)\n",
    "        chs = []\n",
    "        for ch in ascii_lowercase[::-1]:\n",
    "            if cnt[ch] // k:\n",
    "                chs += [ch] * (cnt[ch] // k)\n",
    "        \n",
    "        for l in range(len(chs), 0, -1):\n",
    "            for p in permutations(chs, l):\n",
    "                word = ''.join(p)\n",
    "                ss = iter(s)\n",
    "                if all(c in ss for c in word * k):\n",
    "                    return word\n",
    "\n",
    "        return ''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubsequenceRepeatedK(self, s: str, k: int) -> str:\n",
    "        num = Counter(s)\n",
    "        hot = ''.join(ele * (num[ele] // k) for ele in sorted(num, reverse=True))\n",
    "        for i in range(len(hot), 0, -1):\n",
    "            for item in permutations(hot, i):\n",
    "                word = ''.join(item)\n",
    "                ss = iter(s)\n",
    "                if all(c in ss for c in word * k):\n",
    "                    return word\n",
    "        return ''\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubsequenceRepeatedK(self, s: str, k: int) -> str:\n",
    "        num = Counter(s)\n",
    "        hot = ''.join(ele * (num[ele] // k) for ele in sorted(num, reverse=True))\n",
    "        for i in range(len(hot), 0, -1):\n",
    "            for item in permutations(hot, i):\n",
    "                word = ''.join(item)\n",
    "                ss = iter(s)\n",
    "                if all(c in ss for c in word * k):\n",
    "                    return word\n",
    "        return ''\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubsequenceRepeatedK(self, s: str, k: int) -> str:\n",
    "        num = Counter(s)\n",
    "        hot = ''.join(ele * (num[ele] // k) for ele in sorted(num, reverse=True))\n",
    "        for i in range(len(hot), 0, -1):\n",
    "            for item in permutations(hot, i):\n",
    "                word = ''.join(item)\n",
    "                ss = iter(s)\n",
    "                if all(c in ss for c in word * k):\n",
    "                    return word\n",
    "        return ''\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def match(self, s: str, pattern: str, k: int) -> bool:\n",
    "        total_pattern = pattern * k\n",
    "        i = 0\n",
    "        for c in total_pattern:\n",
    "            while i < len(s) and c != s[i]:\n",
    "                i += 1\n",
    "            if i == len(s):\n",
    "                return False\n",
    "            i += 1\n",
    "        return True        \n",
    "\n",
    "    def longestSubsequenceRepeatedK(self, s: str, k: int) -> str:\n",
    "        char_dict = dict()\n",
    "        chars_list = []\n",
    "        for c in s:\n",
    "            if c in char_dict.keys():\n",
    "                char_dict[c] += 1\n",
    "            else:\n",
    "                char_dict[c] = 1\n",
    "        for c in char_dict.keys():\n",
    "            if char_dict[c] >= k:\n",
    "                chars_list.append(c)\n",
    "        chars_list.sort(reverse=True)\n",
    "        chars = \"\"\n",
    "        for c in chars_list:\n",
    "            chars += c\n",
    "\n",
    "        length = 0\n",
    "        for c in s:\n",
    "            if c in chars:\n",
    "                length += 1\n",
    "        # pattern中只可能有chars中的字符\n",
    "        # pattern最长只能有length // k的长度\n",
    "        # 遍历所有可能的pattern？\n",
    "        max_length = 0\n",
    "        max_pattern = \"\"\n",
    "        index = 0\n",
    "        while index < len(chars) ** (length // k):\n",
    "            pattern = \"\"\n",
    "            tmp = index\n",
    "            for _ in range(length // k):\n",
    "                c = chars[tmp % len(chars)]\n",
    "                pattern = c + pattern\n",
    "                tmp //= len(chars)\n",
    "            \n",
    "            for i in range(max_length, len(pattern)):\n",
    "                sub_pattern = pattern[:i+1]\n",
    "                matched = True\n",
    "                for j in sub_pattern:\n",
    "                    if sub_pattern.count(j) * k > char_dict[j]:\n",
    "                        # 肯定匹配不上\n",
    "                        matched = False\n",
    "                if matched == True and self.match(s, sub_pattern, k):\n",
    "                    max_pattern = sub_pattern\n",
    "                    max_length = len(sub_pattern)\n",
    "                else:\n",
    "                    # sub_pattern匹配不上，那么后面都不用尝试匹配了\n",
    "                    tmp = len(chars) ** (length // k - len(sub_pattern))\n",
    "                    if tmp != 0:\n",
    "                        index += tmp\n",
    "                        index = index // tmp * tmp\n",
    "                    index -= 1\n",
    "                    break\n",
    "            index += 1\n",
    "            if max_length == len(pattern):\n",
    "                return max_pattern\n",
    "        return max_pattern\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubsequenceRepeatedK(self, s: str, k: int) -> str:\n",
    "        ret, cnt, char = [], Counter(s), []\n",
    "        for ch in cnt:\n",
    "            for _ in range(cnt[ch] // k):\n",
    "                char.append(ch)\n",
    "        char = sorted(char)[::-1]\n",
    "        char_set = set(char)\n",
    "        ns = \"\"\n",
    "        for ch in s:\n",
    "            if ch in char_set:\n",
    "                ns = ns + ch\n",
    "\n",
    "        def check(string):\n",
    "            # print(string)\n",
    "            cy, idx = 0, 0\n",
    "            for i, ch in enumerate(s):\n",
    "                if ch == string[idx]:\n",
    "                    idx += 1\n",
    "                    if idx >= len(string):\n",
    "                        idx = 0\n",
    "                        cy += 1\n",
    "                        if cy >= k:\n",
    "                            return True\n",
    "            return False\n",
    "\n",
    "        def perm(string, i):\n",
    "            nonlocal ret\n",
    "            if i >= len(string):\n",
    "                if check(string):\n",
    "                    if len(string) >= len(ret) and ''.join(string) > ''.join(ret):\n",
    "                        ret = string[:]\n",
    "                return\n",
    "            for j in range(i, len(string)):\n",
    "                string[i], string[j] = string[j], string[i]\n",
    "                a = perm(string, i + 1)\n",
    "                string[i], string[j] = string[j], string[i]\n",
    "\n",
    "        def choose_r(string, avb, r):\n",
    "            if len(string) == r:\n",
    "                if check(string):\n",
    "                    return string\n",
    "                return\n",
    "            for j in avb:\n",
    "                navb = avb.copy()\n",
    "                navb.remove(j)\n",
    "                string.append(char[j])\n",
    "                a = choose_r(string, navb, r)\n",
    "                if a != None:\n",
    "                    return a\n",
    "                string.pop(-1)\n",
    "\n",
    "\n",
    "        for r in range(len(char), 0, -1):\n",
    "            a = choose_r([], set([i for i in range(len(char))]), r)\n",
    "            if a != None:\n",
    "                return ''.join(a)\n",
    "\n",
    "        return ''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubsequenceRepeatedK(self, s: str, k: int) -> str:\n",
    "        num = Counter(s)\n",
    "        keys = sorted(num, reverse=True)\n",
    "        # print(num)\n",
    "        hot = ''.join(ele * (num[ele] // k) for ele in keys)\n",
    "        for i in range(len(hot), 0, -1):\n",
    "            used = set()\n",
    "            for item in permutations(hot, i): \n",
    "                word = ''.join(item)\n",
    "                if word is used: continue\n",
    "                used.add(word)\n",
    "                ss = iter(s)\n",
    "                if all(c in ss for c in word * k):\n",
    "                    return word\n",
    "        return ''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "from itertools import permutations\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def longestSubsequenceRepeatedK(self, s: str, k: int) -> str:\n",
    "        cnt = Counter(s)\n",
    "        hot = ''.join([w * (cnt[w] // k) for w in sorted(cnt, reverse=True)])\n",
    "        m = len(hot) if len(hot) < 7 else 7\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def check(word):\n",
    "            ss = iter(s)\n",
    "            if all(w in ss for w in word*k):\n",
    "                return True\n",
    "            return False\n",
    "\n",
    "        for i in range(m, 0, -1):\n",
    "            for item in permutations(hot, i):\n",
    "                word = \"\".join(item)\n",
    "                if check(word):\n",
    "                    return word\n",
    "        return ''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestSubsequenceRepeatedK(self, s: str, k: int) -> str:\n",
    "        cnt = Counter(s)\n",
    "        lst = []\n",
    "        for w in cnt:\n",
    "            lst.extend([w]*(cnt[w]//k))\n",
    "        lst.sort(reverse=True)\n",
    "        \n",
    "        @lru_cache(None)\n",
    "        def check(st):\n",
    "            t = st*k\n",
    "            i = 0\n",
    "            n = len(t)\n",
    "            for ww in s:\n",
    "                if i<n and ww == t[i]:\n",
    "                    i += 1\n",
    "            return i == n\n",
    "     \n",
    "        for x in range(7, 0, -1):\n",
    "            for item in permutations(lst, x):\n",
    "                st = \"\".join(item)\n",
    "                if check(st):\n",
    "                    return st\n",
    "        return \"\""
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
